package array;

import java.util.Stack;

/**
 * 给你一个整数数组 nums。在一次操作中，你可以选择一个子数组，并将其替换为一个等于该子数组 最大值 的单个元素。
 * 返回经过零次或多次操作后，数组仍为 非递减 的情况下，数组 可能的最大长度。
 * 子数组 是数组中一个连续、非空 的元素序列。
 * <p>
 * 示例 1：
 * 输入： nums = [4,2,5,3,5]
 * 输出： 3
 * 解释：
 * 实现最大长度的一种方法是：
 * 将子数组 nums[1..2] = [2, 5] 替换为 5 → [4, 5, 3, 5]。
 * 将子数组 nums[2..3] = [3, 5] 替换为 5 → [4, 5, 5]。
 * 最终数组 [4, 5, 5] 是非递减的，长度为 3。
 * <p>
 * 示例 2：
 * 输入： nums = [1,2,3]
 * 输出： 3
 * 解释：
 * 无需任何操作，因为数组 [1,2,3] 已经是非递减的。
 *
 * @author Jisheng Huang
 * @version 20250420
 */
public class MakeArrNonDecreasing_100554 {
    /**
     * 合并所有比current小的栈顶元素
     *
     * @param nums the given integer arr
     * @return the number of times to make the array non-decreasing
     */
    public static int maximumPossibleSize(int[] nums) {
        Stack<Integer> stack = new Stack<>();

        for (int num : nums) {
            int current = num;

            // 合并所有比current小顶栈顶元素
            while (!stack.isEmpty() && current < stack.peek()) {
                int popped = stack.pop();

                current = Math.max(current, popped);
            }

            stack.push(current);
        }

        return stack.size();
    }

    public static void main(String[] args) {
        int[] nums = {4, 2, 5, 3, 5};
        System.out.println(maximumPossibleSize(nums));

        nums = new int[]{1, 2, 3};
        System.out.println(maximumPossibleSize(nums));
    }
}
